package demo;

import java.util.*;

/**
 * 三数之和
 */
class Solution6 {
	public List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> result = new ArrayList<>();
		if (nums.length < 3) {
			return result;
		}
		Arrays.sort(nums);
		Set<List<Integer>> set = new HashSet<>();
		for (int i = 0; i < nums.length; i++) {
			int left = i;
			int mid = i + 1;
			int right = nums.length - 1;
			while (mid < right) {
				if (nums[mid] + nums[right] + nums[left] > 0) {
					right--;
				} else if (nums[mid] + nums[right] + nums[left] < 0) {
					mid++;
				} else {
					List<Integer> list = new ArrayList<>();
					list.add(nums[left]);
					list.add(nums[mid]);
					list.add(nums[right]);
					set.add(list);
					// 找到一组答案后同时收缩 继续搜索
					right--;
					mid++;
				}
			}
		}
		for(List<Integer>list:set){
			result.add(list);
		}
		return result;
	}

	public static void main(String[] args) {
		int a[] = new int[]{-1,0,1,2,-1,-4};
		Solution6 solution6 = new Solution6();
		solution6.threeSum(a);
	}
}

